class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        res = 0
        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):
                if grid[i][j] == '1':
                    res += 1
                    self.dfs(grid, i, j)
        return res

    def dfs(self, grid, x, y):
        if x < 0 or y < 0 or x == len(grid) or y == len(grid[0]):
            return
        if grid[x][y] == '1':
            grid[x][y] = '0'
            self.dfs(grid, x + 1, y)
            self.dfs(grid, x - 1, y)
            self.dfs(grid, x, y + 1)
            self.dfs(grid, x, y - 1)
